#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    typedef TreeNode Node;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        int flag = 1;
        vector<vector<int>> ret;
        if (!root)
            return ret;
        queue<Node*> q;
        q.push(root);
        while (q.size()) {
            int sz = q.size();
            vector<int> v;
            for (int i = 0; i < sz; i++) {
                Node* node = q.front();
                q.pop();
                v.push_back(node->val);

                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }

            if (flag % 2) {
                ret.push_back(v);
            }
            else
            {
                reverse(v.begin(), v.end());
                ret.push_back(v);
            }
            flag++;
        }
        return ret;
    }
};